// @algorithm @lc id=146 lang=cpp 
// @title lru-cache

class LRUCache {
    struct Node {
        int key=0, value=0;
        Node *pre=NULL, *next=NULL;
    }
    head, tail;
    unordered_map<int, Node*> cache; /* key => Node* */
    int cap=0, size=0;
public:
    LRUCache(int capacity)
    : cap(capacity)
    , size(0)
    {
        head.next = &tail;
        tail.pre = &head;
    }
    
    int get(int key) {
        if(!cache.count(key))
            return -1;
        auto node = cache[key];
        erase(node);
        push_front(node);
        return node->value;
    }
    
    void put(int key, int value) {
        Node * node = NULL;
        if(cache.count(key)){ // 存在
            node = cache[key];
            erase(node);
        }else{ // 新key
            node = new Node();
            node->key = key;
            cache[key] = node;
            ++size;
            if(cap < size){
                auto last = erase(tail.pre);
                cache.erase(last->key);
                delete last;
                --size;
            }
        }
        node->value = value;
        push_front(node);
    }

    void push_front(Node *node){
        head.next->pre = node;
        node->pre = &head;
        node->next = head.next;
        head.next = node;
    }

    Node* erase(Node *node){
        node->pre->next = node->next;
        node->next->pre = node->pre;
        return node;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */